//
//  23.二叉搜索树的后序遍历序列.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/19.
//

import Foundation
/*
 题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜素树）
 思路：以{5,7,6,9,11,10,8}为例，后序遍历结果的最后⼀个数字8就是根结点的值。在这个数组中，前3个数字5、7和6都⽐8⼩，是值为8的结点的左⼦树结点； 后3个数字9、11和10都⽐8⼤，是值为8的结点的右⼦树结点。 我们接下来⽤同样的⽅法确定与数组每⼀部分对应的⼦树的结构。这其实就是⼀个递归的过程。对于序列5、7、6，最后⼀个数字6是左⼦树的根结点的 值。数字5⽐6⼩，是值为6的结点的左⼦结点，⽽7则是它的右⼦结点。同样，在序列9、11、10中，最后⼀个数字10是右⼦树的根结点，数字9⽐10⼩，是 值为10的结点的左⼦结点，⽽11则是它的右⼦结点。 我们使⽤递归的⽅法，先判断数组的左⼦树和右⼦树的位置，然后再判断左⼦树、右⼦树是不是⼆叉搜索树。
 */
func offer_23() {
    print(Solution().verifySquenceOfBST2([4, 8, 6, 12, 16, 14, 10]))
}

fileprivate class Solution {
    func verifySquenceOfBST1(_ sequence: [Int]) -> Bool {
        // write code here
        guard !sequence.isEmpty else { return false }
        var index = 0
        // 找出左子树的位置
        while sequence[index] < sequence.last! && index < sequence.count {
            index += 1
        }
        // 遍历右子树，右子树必须大于根节点
        for i in index..<sequence.count-1 {
            if sequence[i] < sequence.last! {
                return false
            }
        }
        
        var left = true
        if index > 0 {
            left = verifySquenceOfBST1(Array(sequence[0..<index]))
        }
        var right = true
        if index < sequence.count - 1 {
            right = verifySquenceOfBST1(Array(sequence[index..<sequence.count-1]))
        }
        
        return left && right
    }
}

/*
 方法二：上限约束法
 那么贪婪的我们不禁就会想，有没有更好的方法？？O(n)、甚至O(logn)？

 由于一个正确的遍历序列，我们可以在它任意一个位置故意篡改，因此势必要遍历所有的元素才能确定它的正确性，所以个人认为，这个问题的时间复杂度下界应该就是O(n)。

 具体来说，二叉搜索树的关键特征是：对于任意一棵子树，均有“左子树<根节点<右子树”，因此，它的根节点约束了它左右子树的取值范围，二叉搜索树的根root是它左子树值的上限（max），同时是它右子树值的下限（min）。如果我们从根节点出发往下走，那么高层祖辈节点序列就会不停地对低层未遍历节点形成一个上下限约束，只要低层节点没有违背这个约束，那么它就是合法的，否则，序列就是不合法的。

 因为后序遍历的一些特性，我们可以从右到左倒序访问给定的序列，因为后序遍历的最后一个元素是根节点，倒序访问就相当于是从根到叶，从右到左的访问顺序，从根到叶可以让我们利用祖辈节点提供的上下限约束信息来判断孩子节点合法性，具体步骤如下：

 如果当前元素 > 上一个元素，这说明当前元素可能是上一个元素的右孩子，这时候：
 如果当前元素突破max上限约束，说明祖辈中存在 “左子树 > 根” 的情况，违背了搜索树的定义（尝试把图中4的值换成7，那么就有子辈7 > 祖辈max约束5，搜索树不成立）；
 否则，当前元素就是上一个元素的右孩子，当前元素将成为新的祖辈节点，为后续节点提供约束；
 如果当前元素 < 上一个元素，这就说明当前元素是某个祖辈节点的左孩子，这时候：
 我们需要找出这个祖辈节点，并将该祖辈的右子树节点全部丢弃（因为它的右子树结构已经确定，无法为后续节点提供帮助），该祖辈节点的值将成为新的max上限约束，
 当前元素将成为新的祖辈节点，继续为后续节点提供约束；
 */
extension Solution {
    func verifySquenceOfBST2(_ sequence: [Int]) -> Bool {
        guard !sequence.isEmpty else { return false }
        // roots栈里面依次存放各层祖辈节点的值
        // 事先放入一个值以避免对空栈进行判断
        var stack = [Int]()
        stack.append(Int.min)
        // 初始约束，使整个树在左子树中，在左子树中判断
        var max = Int.max
        for i in (0..<sequence.count).reversed() {
            // 当节点大于max约束时，肯定不是二叉搜索树
            if sequence[i] > max { return false }
            // 如果节点小于roots的栈顶，说明该节点是某个祖辈的左孩子
            // 不断出栈，直到找出该祖辈，同时，该祖辈也提供了新的max约束
            while sequence[i] < stack.last! {
                max = stack.removeLast()
            }
            // 该节点成了新一代的祖辈节点，为后续节点判断自己的位置提供依据
            stack.append(sequence[i])
        }
        return true
    }
}
